图 Graph
1.图的定义
顶点用边连起来就是图
由不相交的顶点集与边集组成( G = ( V , E ) )的非线性数据结构
其中E是边的有穷集,V是顶点的有穷非空集
无向图
边没有方向的图称为无向图
有向图
边有方向的图称为有向图
度
与节点关联的边数,在有向图中为出度与入度之和
出度
在有向图中以这个结点为起点的有向边的数目
入度
在有向图中以这个结点为终点的有向边的数目
任意一个图的总度数等于其边数的两倍
权值
与边相关的值(长度或者费用等)
2.图的存储
二维数组储存结构:邻接矩阵
无向图邻接矩阵
拥有n个顶点的图, 它所包含的连接数量最多是n(n - 1) / 2个,因此要表达各个顶点之间的关联关系,最清晰易懂的方式是使用二维数组(矩阵)
$$
\matrix{
&v0&v1&v2&v3\
v0&0&1&1&1\
v1&1&0&0&1\
v2&1&0&0&1\
v3&1&1&1&0\
}
$$
该矩阵表示由结点0,1,2,3两两相连的无向图
观察矩阵不难发现,
(1)无向图的邻接矩阵是对称的
(2)顶点i的度等于第i行(列)中1的个数
(3)完全图的邻接矩阵中,对角元素为0,其余全1
即,g$[i][j] = 1$表示结点i与结点j相连
有向图邻接矩阵
与无向图邻接矩阵差异不大,只不过在无向图中结点1与2相连表示为$g[1][2] = 1 ; g[2][1] = 1$ ,有向图中结点1指向结点2则表示为$g[1][2] = 1 ; g[2][1] = 0 $
比如,表示一张1指向2,1指向3,3指向4,4指向1的图可以为:
$$
\matrix{
&v1&v2&v3&v4\
v1&0&1&1&0\
v2&0&0&0&0\
v3&0&0&0&1\
v4&1&0&0&0\
}
$$
观察分析可以得出,
(1)有向图的邻接矩阵可能是不对称的
(2)顶点的出度 = 第i行元素之和,顶点的入度 = 第i列元素之和
代码实现
给出一个包含无向图和有向图的混合图G,图上有n个点m条边,使用邻接矩阵储存并输出该邻接矩阵,输入a, x, y表示x和y之间有一条边,若a = 1则为无向边,反之则为有向边
1 |
|
输入
1 | 4 4 |
输出
1 | 0 1 1 0 |
有权图的邻接矩阵
与上面的有向图或无向图相同,把1改为权值即可,但是没有相连即没有边的结点不能用0来表示,所有初始化要用inf无穷来表示,在c语言中可以用0x3f
(较大数,也可用0x7f
但是可能会爆int)
总结
优点:容易实现图的操作,如求某顶点的度,判断顶点之间是否有边,找顶点的邻接点等
缺点:空间效率为$$O(n^2)$$,对稀疏图尤其浪费空间,建议数据量小于100时使用,或可配合佛洛依德算法(三重循环)求最短路径等
链表(含数组模拟链表)存储结构
邻接表(链表存点)
对每个顶点$vi$建立一个单链表,把与$vi$有关联的边的信息(即入度边或者出度边)链接起来(注意边没有顺序)
这里使用数组模拟链表法:
h[]
数组:顶点数组,保存链表第一个链接顶点下标
nxt[]
数组:模拟指针数组,下标指向顶点编号,权值等值指向下一个nxt[]
位置,若‘-1’则说明没有后继
vtx[]
数组:边数组,保存这条边指向的节点
变量idx = 0
代码实现(模版):
连边:
1 | int h[N], vtx[2*N], nxt[2*N], idx = 0;//N视情况而定 |
3.图的遍历
(1)深度优先遍历(dfs)
图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。
假设初识状态是图中所有顶点均未被访问,则从某个顶点V出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
显然,深度优先搜索是一个递归的过程
深度优先遍历特点是,选定一个出发点后进行遍历,能前进则前进,若不能前进,回退一步再前进,或再回退一步后继续前进。依此重复,直到所有与选定点相通的所有顶点都被遍历。
代码实现
准备工作:创建一个visited数组,用于记录所有被访问过的顶点。
1.从图中v0出发,访问v0。
2.找出v0的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复此步骤,直至刚访问过的顶点没有未被访问的邻接点为止。
3.返回前一个访问过的仍有未被访问邻接点的顶点,继续访问该顶点的下一个未被访问领接点。
4.重复2,3步骤,直至所有顶点均被访问,搜索结束。
模版:
1 | //接上文邻接表的数组定义 |
未完待续……
- 本文作者: Phquathi
- 本文链接: http://phquathi.github.io/pHq-blog/2024/05/20/图 Graph/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!